import java.util.Arrays;

/**
 * 1605. 给定行和列的和求可行矩阵
 * https://leetcode-cn.com/problems/find-valid-matrix-given-row-and-column-sums/
 */
public class Solutions_1605 {
    public static void main(String[] args) {
//        int[] rowSum = {3, 8}, colSum = {4, 7};  // output: {{3, 0}, {1, 7}}
//        int[] rowSum = {5, 7, 10}, colSum = {8, 6, 8};  // output: {{0, 5, 0}, {6, 1, 0}, {2, 0, 8}}
        int[] rowSum = {14, 9}, colSum = {6, 9, 8};  // output: {{0, 9, 5}, {6, 0, 3}}
//        int[] rowSum = {1, 0}, colSum = {1};  // output: {{1},  {0}}
//        int[] rowSum = {0}, colSum = {0};  // output: {{0}}

        int[][] result = restoreMatrix(rowSum, colSum);
        System.out.println(Arrays.deepToString(result));
    }

    /**
     * 解题思路：贪心算法
     * 以 rowSum = {3, 8}, colSum = {4, 7} 为例：
     * 第一行的和为 3，第一列的和为 4
     * 那么 res[0][0] 的值，最大为 Math.min(3, 4) = 3
     * 赋值后，行列的和也相应地做减法，rowsum[0] -= 3，colSum[0] -= 3
     */
    public static int[][] restoreMatrix(int[] rowSum, int[] colSum) {
        int rows = rowSum.length, cols = colSum.length;
        int[][] res = new int[rows][cols];
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                if (rowSum[i] != 0 && colSum[j] != 0) {
                    // 最较小的数字
                    res[i][j] = Math.min(rowSum[i], colSum[j]);
                    // 同时对应的行和列需要减去该数字
                    rowSum[i] -= res[i][j];
                    colSum[j] -= res[i][j];
                }
            }
        }
        return res;
    }
}
